class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        result = []
        s_len = len(s)
        fp = 0
        while fp < s_len:
            bp = fp
            max_bp = bp
            while bp+1 < s_len:
                bp += 1
                if s[bp] == s[fp]:
                    max_bp = bp
            if max_bp == fp:
                result.append(1)
                fp += 1
                continue
            i = fp + 1
            while i < max_bp:
                j = max_bp + 1
                while j < s_len:
                    if s[i] == s[j]:
                        max_bp = j
                    j += 1
                i += 1
            result.append(max_bp-fp+1)
            fp = max_bp + 1
        return result
    
    def partitionLabels_2(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        result = []
        s_len = len(s)
        last_index = [0] * 26
        for i in range(s_len):
            last_index[ord(s[i]) - ord('a')] = i
        fb = 0
        while fb < s_len:
            end = fb
            for i in range(fb, s_len):
                end = max([end, last_index[ord(s[i]) - ord('a')]])
                if i == end:
                    result.append(end-fb+1)
                    break
            fb = end + 1
        return result

